46. 全排列

Similar Question

Solution Tips

方案一: 回溯 + N 叉树

本质就是每次删除, rest 越来越少, 从 index 0 开始遍历, 越遍历越少

var permute = function (nums) {
    const res = [];
    dfs([], nums);
    return res;

    function dfs(chosen, rest) {
        if (chosen.length === nums.length) {
            res.push([...chosen])
            return;
        }

        if (curIndex > rest.length - 1) {
            return;
        }

        // index 每次都是从 0 开始
        for (let i = 0; i < rest.length; i++) {
            chosen.push(rest[i])
			// 删除 i
            const newRest = rest.slice(0, i).concat(rest.slice(i + 1));
            dfs(chosen, newRest);
            chosen.pop();
        }
    }
}
console.log(permute([1,2,3]))

方案二: 回溯 + 二元思路

var permute = function (nums) {
    const res = [];
    dfs([], nums, 0);
    return res;

    function dfs(chosen, rest, curIndex) {
        if (chosen.length === nums.length) {
            res.push([...chosen])
            return;
        }

        if (curIndex > rest.length - 1) {
            return;
        }

        // 选了
        chosen.push(rest[curIndex])
        const newRest = rest.slice(0, curIndex).concat(rest.slice(curIndex + 1));
        dfs(chosen, newRest, 0);
        chosen.pop();
        // 没选
        dfs(chosen, rest, curIndex + 1);
    }
}
console.log(permute([1,2,3]))

方案三: 使用 Used 数组

var permute = function(nums) {
    const res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;
    
    function backtracking(n, k, used) {
        if(path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++ ) {
            if(used[i]) continue;
            path.push(n[i]);
            used[i] = true; // 同支
            backtracking(n, k, used);
            path.pop();
            used[i] = false;
        }
    }
};

方案四: 利用已经排列的空间

每次将使用过的数字交换到最前面, 每次都从 newIndex 开始遍历, 就可以节省一下空间复杂度

参考官方题解: Loading Question... - 力扣（LeetCode）

可以用这个思路去优化二元方案里的剪枝策略